package 动态规划.背包问题;
import java.util.Scanner;
/*完全背包状态转移方程式*/

/**
 *  01背包问题每个物品只能拿一次，完全背包问题每个物品能拿无数次
 * 	（最朴素的方法就是再加一层循环）
 * */
public class 完全背包问题 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int m=sc.nextInt();
		int n=sc.nextInt();
		int[][] dp=new int[n+1][m+1];
		int[] w=new int[n+1];
		int[] c=new int[n+1];
		for(int i=1;i<=n;i++) {
			w[i]=sc.nextInt();
			c[i]=sc.nextInt();
		}
		long begin,end;
		begin=System.currentTimeMillis();
		for(int x=1;x<=n;x++)
			for(int y=1;y<=m;y++) {
				if(y<w[x])
					dp[x][y]=dp[x-1][y];
				else
					//（重点）状态转移方程式
					dp[x][y]=max(dp[x-1][y],dp[x][y-w[x]]+c[x]);
				//注意：如果选择拿当前物品，01背包的价值  是容量为y时上一个物品最优解+当前物品
				//完全背包的价值是 容量为y-w[x]时当前物品最优解+当前物品
			}
		for(int i[]:dp) {
			for(int j:i) {
				System.out.print(j+" ");
			}
			System.out.println();
		}
		System.out.println("最多能拿"+dp[n][m]+"元");
		end=System.currentTimeMillis();
		System.out.println("耗时"+(end-begin));
		sc.close();
	}

	private static int max(int i, int j) {
		return i>j?i:j;
	}
}
